<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Hard
  </div>
  <div>
   <h1 class="question_title">
    72. Edit Distance
   </h1>
   <p>
    Given two words
    <em>
     word1
    </em>
    and
    <em>
     word2
    </em>
    , find the minimum number of operations required to convert
    <em>
     word1
    </em>
    to
    <em>
     word2
    </em>
    .
   </p>
   <p>
    You have the following 3 operations permitted on a word:
   </p>
   <ol>
    <li>
     Insert a character
    </li>
    <li>
     Delete a character
    </li>
    <li>
     Replace a character
    </li>
   </ol>
   <p>
    <strong>
     Example 1:
    </strong>
   </p>
   <pre>
<strong>Input:</strong> word1 = "horse", word2 = "ros"
<strong>Output:</strong> 3
<strong>Explanation:</strong> 
horse -&gt; rorse (replace 'h' with 'r')
rorse -&gt; rose (remove 'r')
rose -&gt; ros (remove 'e')
</pre>
   <p>
    <strong>
     Example 2:
    </strong>
   </p>
   <pre>
<strong>Input:</strong> word1 = "intention", word2 = "execution"
<strong>Output:</strong> 5
<strong>Explanation:</strong> 
intention -&gt; inention (remove 't')
inention -&gt; enention (replace 'i' with 'e')
enention -&gt; exention (replace 'n' with 'x')
exention -&gt; exection (replace 'n' with 'c')
exection -&gt; execution (insert 'u')
</pre>
  </div>
  <div>
   <h1 class="question_title">
    72. 编辑距离
   </h1>
   <p>
    给定两个单词&nbsp;
    <em>
     word1
    </em>
    和&nbsp;
    <em>
     word2
    </em>
    ，计算出将&nbsp;
    <em>
     word1
    </em>
    &nbsp;转换成&nbsp;
    <em>
     word2
    </em>
    所使用的最少操作数&nbsp;。
   </p>
   <p>
    你可以对一个单词进行如下三种操作：
   </p>
   <ol>
    <li>
     插入一个字符
    </li>
    <li>
     删除一个字符
    </li>
    <li>
     替换一个字符
    </li>
   </ol>
   <p>
    <strong>
     示例&nbsp;1:
    </strong>
   </p>
   <pre><strong>输入:</strong> word1 = "horse", word2 = "ros"
<strong>输出:</strong> 3
<strong>解释:</strong> 
horse -&gt; rorse (将 'h' 替换为 'r')
rorse -&gt; rose (删除 'r')
rose -&gt; ros (删除 'e')
</pre>
   <p>
    <strong>
     示例&nbsp;2:
    </strong>
   </p>
   <pre><strong>输入:</strong> word1 = "intention", word2 = "execution"
<strong>输出:</strong> 5
<strong>解释:</strong> 
intention -&gt; inention (删除 't')
inention -&gt; enention (将 'i' 替换为 'e')
enention -&gt; exention (将 'n' 替换为 'x')
exention -&gt; exection (将 'n' 替换为 'c')
exection -&gt; execution (插入 'u')
</pre>
  </div>
 </body>
</html>